/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/unique-binary-search-trees
   @Language: C++
   @Datetime: 19-07-10 10:55
   */

class Solution {
public:
	int numTrees(int n) {
		long h=1;   // catalan h(n)=C(2n,n)/(n+1)=h(n-1)*(4n-2)/(n+1)
		for(long i=1; i++<n; h=h*(4*i-2)/(i+1));
		return h;
	}
};
